package Midium;
// 62.不同路径  dp专项训练 每日一题 4.22
/*
 * 一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？
 * */

import java.util.HashMap;
import java.util.Map;

/*
 * -------------------------------------------------------------
 * 暴力深搜思路：
 * 初始化n*m的boolean矩阵，true代表还可以使用，false代表当前格子不能使用
 * 每次可以向右移动一格或者向下移动一格，移动后把已经经历过的格子变为false
 * 当到终点的时候，记录路线数目count=count+1,count初始为0
 * 每当不能移动的时候（不能向下或者向右或者已经到终点），退后一格
 * 每次执行退后操作的时候，如C->B->A，C退到B，则将C记录为false不变，然后从B退到A，则将C变为true
 * 即：每次退后的时候，需要记录退后的那个格子的下标，当下一次再退后的时候，将那个下标对应位置变为true
 * -------------------------------------------------------------
 * dp思路：
 * dp[i][j] = dp[i-1][j] + dp [i][j-1]
 * 因为如果有x条路线到目标点的上一个点，则一定有x条路线到目标点
 *    如果有y条路线到目标点的左面的一个点，则一定有y条路线到目标点
 * 因此到目标点的路线就等于到左边的路线数+到上面的路线数
 *  */
public class Solution62 {
    // 先试试暴力解法——深搜
    // 通过率： 37/62 超出时间限制
    // 自测：当达到15*15级别的m*n时，在力扣上就会超时
    public static int uniquePaths_dfs(int m, int n) {
        // 初始化全部为true
        boolean canUse[][] = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                canUse[i][j] = true;
            }
        }
        // 机器人一开始就走过了起点位置
        canUse[0][0] = false;
        // map的value用来记录count个数
        Map count = new HashMap<>();
        int[] last = new int[2];
        last[0] = -1;
        last[1] = -1;
        count.put(1, 0);
        dfs(canUse, count, 0, 0, last);
        return (int) count.get(1);
    }

    // 传入当前机器人所在的位置
    public static void dfs(boolean canUse[][], Map count, int nowX, int nowY, int[] last) {
        // 找到终点，递归结束
        if (nowX == canUse.length - 1 && nowY == canUse[0].length - 1) {
            int i = (int) count.get(1) + 1;
            count.replace(1, i);
            return;
        }
        // 先尽可能向下，然后退回一格
        if (nowX < canUse.length - 1 && canUse[nowX + 1][nowY] == true) {
            nowX++;
            canUse[nowX][nowY] = false;
            dfs(canUse, count, nowX, nowY, last);
            // 退后一格
            if (last[0] == -1 || last[1] == -1) {
                canUse[nowX][nowY] = false; // 还是false不变，但是下一次在任何时候退后的时候，就要变为true了
                last[0] = nowX;
                last[1] = nowY;
                nowX--;
            } else {
                canUse[nowX][nowY] = false; // 还是false不变，但是下一次在任何时候退后的时候，就要变为true了
                canUse[last[0]][last[1]] = true;
                last[0] = nowX;
                last[1] = nowY;
                nowX--;
            }

        }
        // 再尽可能向右，然后退回一格
        if (nowY < canUse[0].length - 1 && canUse[nowX][nowY + 1] == true) {
            nowY++;
            canUse[nowX][nowY] = false;
            dfs(canUse, count, nowX, nowY, last);
            // 退后一格
            if (last[0] == -1 || last[1] == -1) {
                canUse[nowX][nowY] = false; // 还是false不变，但是下一次在任何时候退后的时候，就要变为true了
                last[0] = nowX;
                last[1] = nowY;
                nowY--;
            } else {
                canUse[nowX][nowY] = false; // 还是false不变，但是下一次在任何时候退后的时候，就要变为true了
                canUse[last[0]][last[1]] = true;
                last[0] = nowX;
                last[1] = nowY;
                nowY--;
            }
        }
    }

    public static void main(String[] args) {
        int i = uniquePaths(15, 15);
        System.out.println(i);
    }

    // 开始写dp的方法
    public static int uniquePaths(int m, int n) {
        int dp[][] = new int[m][n];
        dp[0][0] = 1;
        int x = 0;
        int y = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                try {
                    x = dp[i - 1][j];
                } catch (Exception e) {
                    x = 0;
                }
                try {
                    y = dp[i][j - 1];
                } catch (Exception e) {
                    y = 0;
                }
                dp[i][j] = x + y;
            }
        }
        return dp[m - 1][n - 1];
    }
}
